#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}Stack;



typedef struct {
	Stack s1;
	Stack s2;
} MyQueue;

void StackInit(Stack* ps) {
	assert(ps);
	ps->a = NULL;

	ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");

			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top++] = data;

}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

MyQueue* myQueueCreate() {
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&obj->s1);
	StackInit(&obj->s2);
	return obj;
}

void myQueuePush(MyQueue* obj, int x) {
	StackPush(&obj->s1, x);
}

int myQueuePeek(MyQueue* obj) {
	if (StackEmpty(&obj->s2))
	{
		while (!StackEmpty(&obj->s1))
		{
			StackPush(&obj->s2, StackTop(&obj->s1));
			StackPop(&obj->s1);
		}
	}
	return StackTop(&obj->s2);
}


int myQueuePop(MyQueue* obj) {
	int peek = myQueuePeek(obj);
	StackPop(&obj->s2);
	return peek;
}


bool myQueueEmpty(MyQueue* obj) {
	return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->s1);
	StackDestroy(&obj->s2);
	free(obj);
}



typedef struct {
	int* a;
	int head;
	int tail;
	int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

	obj->a = malloc(sizeof(int) * (k + 1));
	obj->head = 0;
	obj->tail = 0;
	obj->k = k;
	return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->tail == obj->head;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->tail + 1) % (obj->k + 1) == obj->head;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))
		return false;
	obj->a[obj->tail] = value;
	obj->tail++;

	obj->tail %= (obj->k + 1);
	return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return false;

	++obj->head;
	obj->head %= obj->k + 1;
	return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return -1;
	return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return -1;
	int rear = obj->tail == 0 ? obj->k : obj->tail - 1;
	return obj->a[rear];
}



void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}